#include <stdio.h>
#include <stdlib.h>
#define N 2147483648

void MinHeapify(unsigned long *A,char **B,int i,int n)
{
  int l=2*i;
  int r=2*i+1;
  int smallest,t;
  char temp[8];
  char *ct=temp;
  if(l<=n && A[l]<=A[i])
  {
    if(A[l]<A[i])
      smallest=l;
    else 
      if(strcmp(B[l],B[i]))
        smallest=i;
      else 
        smallest=l;
  }
  else 
    smallest=i;
  if(r<=n && A[r]<=A[smallest])
  {
    if(A[r]<A[smallest])
      smallest=r;
    else 
      if(!strcmp(B[r],B[smallest]))
        smallest=r;
  }
  if(smallest!=i)
  {
    t=A[i];
    A[i]=A[smallest];
    A[smallest]=t;
    ct=B[i];
    B[i]=B[smallest];
    B[smallest]=ct;
    MinHeapify(A,B,smallest,n);
  }
}

void BuildMinHeap(unsigned long *A,char **B,int n)
{
  int i;
  for(i=n/2;i>=0;i--)
    MinHeapify(A,B,i,n);
}

void Change(unsigned long *A,char **B,int n)
{
  if(A[0]>214748364)   
    A[0]=429496729;
  else
    A[0]=2*A[0];
  MinHeapify(A,B,0,n);
}

int strcmp(char *a,char *b)
{
  int i=0;
  while(a[i]!=0 && b[i]!=0)
  {
   if(a[i]>b[i]) return 1;
   else return 0;
  }
  if(a[i]==0) return 0;
  else return 1;
}